//
//  ProblemOffer13.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/27.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 13. 机器人的运动范围
 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

 示例 1：
     输入：m = 2, n = 3, k = 1
     输出：3
 示例 2：
     输入：m = 3, n = 1, k = 0
     输出：1
 提示：
     1 <= n,m <= 100
     0 <= k <= 20
 */
@objcMembers class ProblemOffer13: NSObject {
    func solution() {
//        print(movingCount(2, 3, 1))
//        print(movingCount(3, 1, 0))
        print(movingCount(10, 6, 6))
        print(movingCount(38, 15, 9))
    }
    

    func movingCount(_ m: Int, _ n: Int, _ k: Int) -> Int {
        var list = Array(repeating: Array(repeating: 0, count: n), count: m)
        return movingCountD(&list, 0, 0, k)
    }
    
    func movingCountD(_ list: inout [[Int]], _ i: Int, _ j: Int, _ k: Int) -> Int {
        if i >= list.count || j >= list[0].count || list[i][j] != 0 {
            return 0
        }
        
        if isOK(i, j, k) == false {
            list[i][j] = -1
            return 0
        }
        list[i][j] = -2
        return movingCountD(&list, i, j+1, k) + movingCountD(&list, i+1, j, k) + 1
    }
    
    func isOK(_ i: Int, _ j: Int, _ k: Int) -> Bool {
        var sum = 0
        
        var si = i
        while si >= 10 {
            sum += si % 10
            si /= 10
        }
        sum += si
        
        if sum > k {
            return false
        }
        var sj = j
        while sj >= 10 {
            sum += sj % 10
            sj /= 10
        }
        sum += sj
        
        return sum <= k
    }
    
    /*
     [69, 50, 41, 33, 26, 20, 15, 11, 8, 6, 35, 26, 18, 11, 5],
     [54, 36, 28, 21, 15, 10, 6, 3, 1, -1, 30, 22, 15, 9, 4],
     [45, 28, 21, 15, 10, 6, 3, 1, -1, -1, 25, 18, 12, 7, 3],
     [37, 21, 15, 10, 6, 3, 1, -1, -1, 0, 20, 14, 9, 5, 2],
     [30, 15, 10, 6, 3, 1, -1, -1, 0, 0, 15, 10, 6, 3, 1],
     [24, 10, 6, 3, 1, -1, -1, 0, 0, 0, 10, 6, 3, 1, -1],
     [19, 6, 3, 1, -1, -1, 0, 0, 0, 0, 6, 3, 1, -1, -1],
     [15, 3, 1, -1, -1, 0, 0, 0, 0, 0, 3, 1, -1, -1, 0],
     [12, 1, -1, -1, 0, 0, 0, 0, 0, 0, 1, -1, -1, 0, 0],
     [10, -1, -1, 0, 0, 0, 0, 0, 0, 0, -1, -1, 0, 0, 0],
     [45, 36, 28, 21, 15, 10, 6, 3, 1, -1, 0, 0, 0, 0, 0],
     [36, 28, 21, 15, 10, 6, 3, 1, -1, -1, 0, 0, 0, 0, 0],
     [28, 21, 15, 10, 6, 3, 1, -1, -1, 0, 0, 0, 0, 0, 0], [21, 15, 10, 6, 3, 1, -1, -1, 0, 0, 0, 0, 0, 0, 0], [15, 10, 6, 3, 1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0], [10, 6, 3, 1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0], [6, 3, 1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [3, 1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [-1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

     
     */
}
